package a14_Sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @Author quan
 * @Description 三路快排
 * @Date 2023/4/30 16:13
 */
public class Demo5_QuickSortThree {
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        quickSort3(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void quickSort3(int[] arr){
        //调用内部方法
        quickSortInternal3(arr,0,arr.length-1);

    }

    /**
     * 三路快排：在一次操作中将所有重复元素一次放在最终位置
     * 然后递归的在大于和小于基准数的自区间快排即可
     * @param arr
     * @param l 数组的开始索引位置
     * @param r 数组的结束索引位置
     */
    private static void quickSortInternal3(int[] arr, int l, int r) {
        //base case
        if(l >= r){
            return;
        }
        //1、定义基准数v
        // 随机交换基准数
        int randomIndex = ThreadLocalRandom.current().nextInt(l,r);
        swap(arr,randomIndex,l);
        int v= arr[l];
        //小于基准数的区间 arr[l+1...It]
        //等于基准数的区间 arr[It+1,i]
        //大于基准数的区间 arr[gt...r]
        //初始化区间位置：区间刚开始都为空
        int It = l;
        int gt = r+1;
        int i = It+1;
        //2、遍历i索引位置的值，判断该值所属的区间
        //终止条件：扫描的位置已经到大于v值的第一个值
        while (i < gt){
            if(arr[i] < v){
                swap(arr,It+1,i);
                It++; //更新区间范围
                i++;
            } else if (arr[i] > v) {
                swap(arr,gt-1,i);
                //更新区间范围
                gt--;
                //注意这里i不能直接++
            } else{
                i++;
            }
        }
        //3、扫描完所有的元素，将基准数v放在等于v的区间内
        swap(arr,l,It);
        //4、递归的遍历左右区间
        quickSortInternal3(arr,l,It-1);
        quickSortInternal3(arr,gt,r);
    }

    //交换函数
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
